In 1967, Moon and Moser proved a tight bound on the critical density ofsquares in squares: any set of squares with a total area of at most 1/2 can bepacked into a unit square, which is tight. The proof requires full knowledge ofthe set, as the algorithmic solution consists in sorting the objects bydecreasing size, and packing them greedily into shelves. Since then, the onlineversion of the problem has remained open; the best upper bound is still 1/2,while the currently best lower bound is 1/3, due to Han et al. (2008). In thispaper, we present a new lower bound of 11/32, based on a dynamic shelfallocation scheme, which may be interesting in itself. We also give results forthe closely related problem in which the size of the square container is notfixed, but must be dynamically increased in order to ac- commodate onlinesequences of objects. For this variant, we establish an upper bound of 3/7 forthe critical density, and a lower bound of 1/8. When aiming for accommodatingan online sequence of squares, this corresponds to a 2.82...- competitivemethod for minimizing the required container size, and a lower bound of 1.33 .. . for the achievable factor.
展开▼
